package _02_并查集;
/*
    QuickUnion
    ✓ 查找（Find）的时间复杂度：O(logN)，可以优化至 O 𝛼 𝑛 ，α(𝑛) < 5
    ✓ 合并（Union）的时间复杂度：O(logN)，可以优化至 O 𝛼 𝑛 ，α(𝑛) < 5

 */
public class QuickUnion extends UnionFind{
    public QuickUnion(int capacity) {
        super(capacity);
    }

    /*
        通过parent不断向上寻找，找到元素所在的根节点，元素自身也是集合
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        while((v!=parents[v])){
            v = parents[v];
        }
        return v;
    }

    /*
        将v1的根节点嫁接到v2的根节点上
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);

        if(p1 == p2) return;

        parents[p1] = p2;
    }
}
